Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.

For example:
Given the below binary tree,

  1.        1
  2.       / \
  3.      2   3

Return 6.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   int max = Integer.MIN_VALUE;
  13.   public int maxPathSum(TreeNode root) {
  14.     helper(root);
  15.     return max;
  16.   }
  18.   int helper(TreeNode root) {
  19.     if (root == null) return 0;
  21.     int left = Math.max(helper(root.left), 0);
  22.     int right = Math.max(helper(root.right), 0);
  24.     max = Math.max(max, root.val + left + right);
  26.     return root.val + Math.max(left, right);
  27.   }
  28. }